package leetcode.N1_N100;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 三数之和
 * https://leetcode-cn.com/problems/3sum/
 *
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例：
 *
 * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 *
 * 满足要求的三元组集合为：
 * [
 *   [-1, 0, 1],
 *   [-1, -1, 2]
 * ]
 *
 */
public class N15 {

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(JSONObject.toJSONString(threeSum(nums)));
    }

    /**
     * 1. 将 a + b + c = 0 的问题转换成 0 - a = b + c
     * 2. 遍历原始数组nums，将当前元素当做a，当前元素右侧的子数组当做待操作数组nums2
     * 3. 从子数组nums2中寻找 b 和 c 使其和等于 0 - a
     * 4. 对获取的三数结果进行去重
     */
    static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        Set<String> set =  new HashSet<>();
        for (int i = 0; i < length - 2; i++) {
            // 提取a
            int a = nums[i];
            // 截取子数组
            int length2 = length - i - 1;
            int[] nums2 = new int[length2];
            System.arraycopy(nums, i + 1, nums2, 0, length2);
            // 从子数组nums2中寻找 b 和 c 使其和等于 0 - a
            // 计算b+c
            int bc = -a;
            Map<Integer, Integer> map = new HashMap<>(length2 / 2 * 3);
            for (int j = 0; j < nums2.length; j++) {
                int b = nums2[j];
                Integer cIndex = map.get(bc - b);
                if (cIndex == null) {
                    map.put(b, j);
                } else {
                    int c = nums2[cIndex];
                    // 去重
                    if (set.add(generateString(a, b, c))) {
                        List<Integer> temp = new ArrayList<>(3);
                        temp.add(a);
                        temp.add(b);
                        temp.add(c);
                        result.add(temp);
                    }
                }
            }
        }
        return result;
    }

    private static String generateString(int a, int b, int c) {
        // 升序排列三个元素 拼接成字符串
        if (a > b) {
            if (b > c) {
                return "" + a + b + c;
            } else if (a > c) {
                return "" + a + c + b;
            } else {
                return "" + c + a + b;
            }
        } else {
            if (a > c) {
                return "" + b + a + c;
            } else if (c > b) {
                return "" + c + b + a;
            } else {
                return "" + b + c + a;
            }
        }
    }

}
